1. Field of the Invention
The present invention concerns a method for estimating the motion between two digital images and to the use of this method for coding images.
The motion between two images, I1 and I2, is generally defined in the form of a field of motion associated with either of the images I1 and I2 and constituted by motion vectors each related to a point of the image concerned. The motion vector is a two dimensional vector representative of the position difference between the pixel of the image I1 and the associated pixel of the image I2 relating to the same physical point of the filmed scene.
The invention can be applied in all fields of imagery requiring an analysis of the movements or disparities between two images. This method can also form part of applying on follow up objects in videos (for the purposes in particular of creating and annotating contents by the objects in a standardisation context MPEG4 and 7).
So as to obtain a motion field, it is known to break down the image into finite elements. These finite elements, which can be triangles or quadrangles, are determined by a mesh whose nodes correspond to the vertices of the finite elements. A motion vector is calculated for each mesh node. Then, via an interpolation function, it is possible to deduce from this a motion vector for each point of the image. The motion field is thus determined by the retained model of finite elements which defines the mesh used to partition the image into finite elements and the interpolation function able to calculate the motion vector at any point of the image.
The mesh used can be regular or irregular and needs to be sufficiently dense so as to model as best as possible the motion between the two images but without requiring an excessive number of calculations or data to be transmitted.
The calculation of the motion vectors of the nodes of the mesh can be carried out according to various methods. First of all, there are matching methods consisting of testing a discrete set of possible values of motion vectors for each node of the mesh and of retaining the best vectors according to a given criterion. A second method known as the transform method consists of using the properties of the Fourier transform and its extensions so as to convert the motion into a phase displacement in the transformed space. Finally, there is a third method known as the differential method which is able to determine the motion vectors by optimising a mathematical criterion (for example by optimising a quadratic error between the image and its value predicted by the motion field). This method is the most used one for the motion estimation with modelising by finite elements. A traditional differential method for optimising motion vectors is the Gauss-Newton method. The present application concerns more particularly the motion estimation method family using a model of finite elements and a differential method by optimising a prediction error for determining the field of motion.
Although widely prevalent, this type of method does have one major drawback. Under the effect of the field of the motion vectors of the nodes of the mesh, the initial mesh on the start image is transformed into a new mesh on the other image. Then mesh overturnings may occur. In fact, the ductile mesh used to partition the image defines a continuous representation of a field of motion, whereas the real motion of the filmed scene is naturally discontinuous. Various elements of the scene can appear or disappear from one image to another, which then generate discontinuities. This is expressed at the level of the meshing by a pulling or an overturning or an overlapping of the meshes of the model. A mesh overturning and overlapping example is illustrated by the FIGS. 1A and 1B. FIG. 1A shows a ductile triangular meshing before applying motion vectors to the nodes of this meshing, and FIG. 1B shows the same meshing after applying said motion vectors. Four nodes with the references A, B, C and D are indicated on these figures. These nodes constitute the vertices of two triangles ABC and BCD. The triangle ABC is hatched on the two figures. It can be observed that, after applying the motion vectors (FIG. 1B), the triangle ABC has overturned and all the triangles whose vertex is the node A cover the triangle BCD, thus destroying the continuity property any meshing needs to check. This overlapping of meshes then brings about a visual deterioration. Thus, one aim of the invention is to eliminate this visual deterioration.
2. Description of the Related Art
At the present time, there are two techniques for resolving these mesh overturning problems: one technique known as the “post-processing” technique and the technique consisting of establishing non-overturning constraints when estimating the motion.
The “post-processing” technique can be implemented according to two possible scenarios: the first scenario corresponding to an a posteriori correction consists of applying as such the calculated motion vectors, of detecting the faulty motion vectors, and then of correcting their value so as to inhibit the overturnings; the second scenario consists of proceeding in an iterative way by applying at each iteration a portion of the expected motion to the nodes so that there is no overturning and by thus looping until the process has converged. However, given the fact that the post-processing methods act once the motion estimation is achieved, the result is sub-optimum because the motion vectors are corrected independently of their global contribution in minimising the prediction error.
Another solution consists of optimising the motion field by integrating non-overturning constraints of the triangles when estimating the motion vectors. The motion estimation is modified by adding to the prediction quadratic error an augmented Lagrangian for correcting the deformation of the triangles when the latter approach the zero area triangle. This technique is described in the article entitled “Limitation of triangles overlapping in mesh-based motion estimation using augmented Lagrangian”, International Conference Image Processing, Chicago, October 1998. This latter technique would effectively make it possible to determine the optimum solution to the problem if the motion field were continuous, which is not the case.